def solve(l: list, k: int):
    count = 0
    for e in l:
        count += e // 3
    if count < k: return -1
    count = 0
    l.sort(reverse=True)
    for e in l:
        if k > 0:
            if e // 3 >= k:
                count += 3 * k - 1
                k = 1
            elif e < 3:
                count += e
            else:
                if e % 3 == 0:
                    count += e - 1
                    k -= e // 3 - 1
                if e % 3 == 1:
                    count += e-2
                    k -= e // 3 - 1
                if e % 3 == 2:
                    count += e
                    k -= e // 3
    return count+1


t = int(input())
for i in range(t):
    n, k = list(map(int, input().split()))
    dic = dict()
    for j in range(n):
        key, v = list(map(int, input().split()))
        dic[key] = dic.get(key, 0) + v
    l = list(dic.values())
    print(solve(l, k))
